Back to course home
0% completed
Vote For New Content
Microsoft Hard Problems
Regular Expression Matching (hard)
Solution: Regular Expression Matching
First Missing Positive (hard)
Solution: First Missing Positive
Largest Rectangle in Histogram (hard)
Solution: Largest Rectangle in Histogram
Sliding Window Maximum (hard)
Solution: Sliding Window Maximum
Count Unique Characters of All Substrings of a Given String (hard)
Solution: Count Unique Characters of All Substrings of a Given String
Word Ladder (hard)
Solution: Word Ladder
Word Ladder II (hard)
Solution: Word Ladder II
Number of Flowers in Full Bloom (hard)
Solution: Number of Flowers in Full Bloom
Median of Two Sorted Arrays (hard)
Solution: Median of Two Sorted Arrays
Longest Valid Parentheses (hard)
Solution: Longest Valid Parentheses
Distribute Coins in Binary Tree (medium)
Problem Statement
You are given a root node of the binary tree, having n nodes, where each node contains the node.val number of coins. There are total n coins in the whole tree.
In one move, you can choose any two adjacent nodes and move a coin from one node to another. You can either move coins from parent to child or child to parent.
Return the minimum number of moves required to ensure every node has exactly one coin.
Examples
Example 1:
- Input: [1,0,2]
- Expected Output: 2
- Justification: We can move one coin from the right child to the root, and then from the root to the left child. This requires 2 moves to balance the coins.
Example 2:
- Input:
[2,0,2,2,0,0]
- Expected Output: 4
- Justification: Move one coin from the root node to its left node, which requires 1 move. After that, move one coin from root->left->left to root->left->right node, which requires 2 moves. Next, move one coin from root->right to root->right->left, which requires 1 move. Minimum number of moves required is
4.
Example 3:
- Input:
[4,0,0,0]
- Expected Output: 4
- Justification: Move two coins from the root to its left child, and then move one coin from this left child to its left child. This requires 3 moves. Move 1 coin to the right child, and this requires 1 move. So, total 4 moves are required.
Try it yourself
Try solving this question here:
Java
Saved to Cloud
. . . .
Solution: Inorder Successor in BST
Solution: Distribute Coins in Binary Tree
Mark as Completed
On this page
Problem Statement
Examples
Try it yourself